package leetcode.other.p33;

class Solution2 {
    /**
     * 右边界收缩条件
     * @param nums
     * @return
     */
    public boolean isRightBoundShink(int[] nums, int mid, int target) {
        int rBound = nums[nums.length - 1];
        // 以下三种情况右边界需要收缩
        // 情况1：nums[mid]在左边递增序列，target也在左边递增序列，nums[mid]>=target
        /*if (nums[mid] > rBound && target > rBound && nums[mid] >= target) {

        }
        // 情况2：nums[mid]在右边递增序列，target在左边递增序列
        if (nums[mid] <= rBound && target > rBound) {

        }
        // 情况3：nums[mid]在右边递增序列，target也在右边递增序列，nums[mid]>=target
        if (nums[mid] <= rBound && target <= rBound && nums[mid] >= target) {

        }*/
        // 整理条件
        if (nums[mid] > rBound) {
            return target > rBound && nums[mid] > target;
        } else {
            return (target < rBound && nums[mid] > target) || target > rBound;
        }
    }
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (isRightBoundShink(nums, mid, target)) { // r收缩
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        //示例 1：
        //输入：nums = [4,5,6,7,0,1,2], target = 0
        //输出：4
        /*System.out.println(new Solution2().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        //示例 2：
        //输入：nums = [4,5,6,7,0,1,2], target = 3
        //输出：-1
        System.out.println(new Solution2().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));
        //示例 3：
        //输入：nums = [1], target = 0
        //输出：-1
        System.out.println(new Solution2().search(new int[]{1}, 0));
        //示例 4：
        //输入：nums = [1,3,5], target = 3
        //输出：1
        System.out.println(new Solution2().search(new int[]{1, 3, 5}, 3));*/
        //示例 5：
        //输入：nums = [5,1,3], target = 5
        //输出：0
        System.out.println(new Solution2().search(new int[]{5, 1, 3}, 5));
    }
}